package tree;

/**
 * description:
 * author:张腾
 * date:2021-04-04
 */

import list.Queue;

/**
 * 二叉查找树（二叉排序树）  使用链表实现
 * 结点的值都大于左子树的任一结点的值，小于右子树任一结点的值
 * 树主要体现的是递归思想
 * @param <Key>
 * @param <Value>
 *
 * 二叉排序树是为了实现动态查找而设计的数据结构，它是面向查找操作的，在二叉排序树中查找一个结点的平均时间复杂度是O(log n)
 */
public class BinaryTree<Key extends Comparable<Key>,Value> {
    //记录根节点
    private Node root;
    //记录树中元素的个数
    private int N;

    private class Node{
        public Key key;  //键
        private Value value;  //值
        public Node left;  //左子节点
        public Node right;  //右子节点

        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    public int size(){
        return N;
    }

    //往树添加元素
    public void put(Key key,Value value){
        root = put(root,key,value);
    }

    //向指定的树x添加key-value，并返回添加元素后的树
    public Node put(Node x,Key key,Value value){
        //如果x子树为空
        if (x==null){
            N++;
            return new Node(key,value,null,null);
        }

        //如果x子树不为空 则比较x节点的键和key的大小

        int cmp = key.compareTo(x.key);
        if (cmp>0){
            //大于，则key值大，需要放在x结点的右子树
            x.right = put(x.right,key,value);
        }else if (cmp<0){
            x.left = put(x.left,key,value);
        }else{
            //等于，则直接替换x的value
            x.value = value;
        }

        return x;
    }

    //查询树中指定key的value
    public Value get(Key key){
        return get(root,key);
    }

    //从指定的树x，查找key对应的值
    public Value get(Node x,Key key){
        if (x==null){
            return null;
        }

        int cmp = key.compareTo(x.key);
        if (cmp>0){
            return get(x.right.key);
        }else if (cmp<0){
            return get(x.left,key);
        }else{
            return x.value;
        }
    }

    public void delete(Key key){
        delete(root,key);
    }

    //删除指定树x的key对应的值，
    public Node delete(Node x,Key key){
        if (x==null){
            return null;
        }

        int cmp = key.compareTo(x.key);
        if (cmp>0){
            //key大于节点的key,则找x节点的右子树
            x.right = delete(x.right,key);
        }else if (cmp<0){
            x.left = delete(x.left,key);
        }else{
            //x等于节点的key，即要删除的节点为x，则执行真正的删除操作
            N--;
            if (x.right==null){
                return x.left;
            }
            if (x.left==null){
                return x.right;
            }

            Node minNode = x.right;
            //找到右节点中的最小的节点即minNode（用来替换x）
            while (minNode.left!=null){
                minNode = minNode.left;
            }

            //找到后，先将其在右子树中删除：删除右节点中的最小节点（即minNode）
            Node n = x.right;
            while (n.left!=null){
                //n的左节点没有左节点，即n的左节点就是最小的节点，先将其删除
                if (n.left.left==null){
                    n.left = n.left.right;
                }else{
                    n = n.left;
                }
            }

            //然后让x的左右子树成为minNode的左右子树，即minNode替代x的位置
            minNode.left = x.left;
            minNode.right = x.right;
            //让x的父节点指向minNode
            x = minNode;

        }
        return x;
    }


    /**
     * 前序遍历 先根再左节点再右节点
     * @return
     */
    //获取整棵树所有的键
    public Queue<Key> preErgodic(){
        Queue<Key> keys = new Queue<>();
        preErgodic(root,keys);
        return keys;
    }
    //获取指定树x中所有的键，并放到key队列中
    public void preErgodic(Node x,Queue<Key> keys){
        if (x==null){
            return ;
        }

        keys.enqueue(x.key);
        if (x.left!=null){
            preErgodic(x.left,keys);
        }
        if (x.right!=null){
            preErgodic(x.right,keys);
        }
    }

    /**
     * 中序遍历 先左节点再根再右节点
     * @return
     */
    //获取整棵树所有的键
    public Queue<Key> midErgodic(){
        Queue<Key> keys = new Queue<>();
        midErgodic(root,keys);
        return keys;
    }
    //获取指定树x中所有的键，并放到key队列中
    public void midErgodic(Node x,Queue<Key> keys){
        if (x==null){
            return ;
        }
        if (x.left!=null){
            midErgodic(x.left,keys);
        }
        keys.enqueue(x.key);
        if (x.right!=null){
            midErgodic(x.right,keys);
        }
    }

    /**
     * 后序遍历 先左节点再右节点再根
     * @return
     */
    //获取整棵树所有的键
    public Queue<Key> afterErgodic(){
        Queue<Key> keys = new Queue<>();
        afterErgodic(root,keys);
        return keys;
    }
    //获取指定树x中所有的键，并放到key队列中
    public void afterErgodic(Node x,Queue<Key> keys){
        if (x==null){
            return ;
        }
        if (x.left!=null){
            afterErgodic(x.left,keys);
        }
        if (x.right!=null){
            afterErgodic(x.right,keys);
        }
        keys.enqueue(x.key);
    }

    /**
     * 层序遍历 按每一层从左往右再从上往下遍历
     * @return
     */
    public Queue<Key> layerErgodic(){
        //两个队列，分别存储树中的键和节点
        Queue<Key> keys = new Queue<>();
        Queue<Node> nodes = new Queue<>();

        //默认情况下，在队列中放入根节点
        nodes.enqueue(root);

        while (!nodes.isEmpty()){
            //从队列中弹出一个节点，把key放入keys中
            Node n = nodes.dequeue();
            keys.enqueue(n.key);
            //如果当前节点还有左节点，则继续把子节点放入nodes中
            if (n.left!=null){
                nodes.enqueue(n.left);
            }
            if (n.right!=null){
                nodes.enqueue(n.right);
            }
        }
        return keys;
    }



    public int maxDepth(){
        return maxDepth(root);
    }

    public int maxDepth(Node x){
        if (x==null){
            return 0;
        }

        int max = 0; //x的最大深度
        int maxL = 0;  //x的左子树的最大深度
        int maxR = 0;  //x的右子树的最大深度

        if (x.left!=null){
            maxL = maxDepth(x.left);
        }
        if (x.right!=null){
            maxR = maxDepth(x.right);
        }

        max = maxL>maxR?maxL+1:maxR+1;

        return max;
    }
}
